Number theoretic transform.md

categories
Number theory, Algorithms

A number theoretic transform is similar to a [fast Fourier transform](Fast Fourier transform), but instead of using complex [roots of unity](Root of unity), [roots of unity modulo $n$](Root of unity modulo n) are used. This allows computing convolutions where arithmetic is taken modulo $n$, and thus avoids using floating point numbers as is the case for fast Fourier transform.

Problems

• Counting tuples

See also

• Fast Fourier transform
• Divide and conquer

External links

• Number theoretic transforms
• A week that ends with FFT
• Fast convolution for 64-bit integers